The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(2^n, INF).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

qsort(nil) → nil
qsort(.(x, y)) → ++(qsort(lowers(x, y)), .(x, qsort(greaters(x, y))))
lowers(x, nil) → nil
lowers(x, .(y, z)) → if(<=(y, x), .(y, lowers(x, z)), lowers(x, z))
greaters(x, nil) → nil
greaters(x, .(y, z)) → if(<=(y, x), greaters(x, z), .(y, greaters(x, z)))

Rewrite Strategy: INNERMOST

(1) RenamingProof (EQUIVALENT transformation)

Renamed function symbols to avoid clashes with predefined symbol.

(2) Obligation:

Runtime Complexity Relative TRS:
The TRS R consists of the following rules:

qsort(nil) → nil
qsort(.(x, y)) → ++(qsort(lowers(x, y)), .(x, qsort(greaters(x, y))))
lowers(x, nil) → nil
lowers(x, .(y, z)) → if(<=(y, x), .(y, lowers(x, z)), lowers(x, z))
greaters(x, nil) → nil
greaters(x, .(y, z)) → if(<=(y, x), greaters(x, z), .(y, greaters(x, z)))

S is empty.
Rewrite Strategy: INNERMOST

(3) SlicingProof (LOWER BOUND(ID) transformation)

Sliced the following arguments:
./0
lowers/0
greaters/0
if/0
<=/0
<=/1

(4) Obligation:

Runtime Complexity Relative TRS:
The TRS R consists of the following rules:

qsort(nil) → nil
qsort(.(y)) → ++(qsort(lowers(y)), .(qsort(greaters(y))))
lowers(nil) → nil
lowers(.(z)) → if(.(lowers(z)), lowers(z))
greaters(nil) → nil
greaters(.(z)) → if(greaters(z), .(y, greaters(z)))

S is empty.
Rewrite Strategy: INNERMOST

(5) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

Infered types.

(6) Obligation:

Innermost TRS:
Rules:
qsort(nil) → nil
qsort(.(y)) → ++(qsort(lowers(y)), .(qsort(greaters(y))))
lowers(nil) → nil
lowers(.(z)) → if(.(lowers(z)), lowers(z))
greaters(nil) → nil
greaters(.(z)) → if(greaters(z), .(y, greaters(z)))

Types:
qsort :: nil:.:++:if:. → nil:.:++:if:.
nil :: nil:.:++:if:.
. :: nil:.:++:if:. → nil:.:++:if:.
++ :: nil:.:++:if:. → nil:.:++:if:. → nil:.:++:if:.
lowers :: nil:.:++:if:. → nil:.:++:if:.
greaters :: nil:.:++:if:. → nil:.:++:if:.
if :: nil:.:++:if:. → nil:.:++:if:. → nil:.:++:if:.
. :: y → nil:.:++:if:. → nil:.:++:if:.
y :: y
hole_nil:.:++:if:.1_0 :: nil:.:++:if:.
hole_y2_0 :: y
gen_nil:.:++:if:.3_0 :: Nat → nil:.:++:if:.

(7) OrderProof (LOWER BOUND(ID) transformation)

Heuristically decided to analyse the following defined symbols:
qsort, lowers, greaters

They will be analysed ascendingly in the following order:
lowers < qsort
greaters < qsort

(8) Obligation:

Innermost TRS:
Rules:
qsort(nil) → nil
qsort(.(y)) → ++(qsort(lowers(y)), .(qsort(greaters(y))))
lowers(nil) → nil
lowers(.(z)) → if(.(lowers(z)), lowers(z))
greaters(nil) → nil
greaters(.(z)) → if(greaters(z), .(y, greaters(z)))

Types:
qsort :: nil:.:++:if:. → nil:.:++:if:.
nil :: nil:.:++:if:.
. :: nil:.:++:if:. → nil:.:++:if:.
++ :: nil:.:++:if:. → nil:.:++:if:. → nil:.:++:if:.
lowers :: nil:.:++:if:. → nil:.:++:if:.
greaters :: nil:.:++:if:. → nil:.:++:if:.
if :: nil:.:++:if:. → nil:.:++:if:. → nil:.:++:if:.
. :: y → nil:.:++:if:. → nil:.:++:if:.
y :: y
hole_nil:.:++:if:.1_0 :: nil:.:++:if:.
hole_y2_0 :: y
gen_nil:.:++:if:.3_0 :: Nat → nil:.:++:if:.

Generator Equations:
gen_nil:.:++:if:.3_0(0) ⇔ nil
gen_nil:.:++:if:.3_0(+(x, 1)) ⇔ .(gen_nil:.:++:if:.3_0(x))

The following defined symbols remain to be analysed:
lowers, qsort, greaters

They will be analysed ascendingly in the following order:
lowers < qsort
greaters < qsort

(9) RewriteLemmaProof (EQUIVALENT transformation)

Proved the following rewrite lemma:
lowers(gen_nil:.:++:if:.3_0(+(1, n5_0))) → *4_0, rt ∈ Ω(2ⁿ)

Induction Base:
lowers(gen_nil:.:++:if:.3_0(+(1, 0)))

Induction Step:
lowers(gen_nil:.:++:if:.3_0(+(1, +(n5_0, 1)))) →_R^Ω(1)
if(.(lowers(gen_nil:.:++:if:.3_0(+(1, n5_0)))), lowers(gen_nil:.:++:if:.3_0(+(1, n5_0)))) →_IH
if(.(*4_0), lowers(gen_nil:.:++:if:.3_0(+(1, n5_0)))) →_IH
if(.(*4_0), *4_0)

We have rt ∈ Ω(2ⁿ) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(2ⁿ)

(10) BOUNDS(2^n, INF)